package ToYesterday.Day10_queue;

public class orderlyQueue {

    private static String strsd;

    public static void main(String[] args) {

//        sort(chars);
        System.out.println(orderlyQueue("baaca",1));
    }
    public static String orderlyQueue(String s, int k) {
        String strsd;
        String minstrsd;
        minstrsd=s;
        char[] strs=new char[s.length()];
        strs = s.toCharArray();
        if (k==1){
            for (int n = 0;n<s.length();n++){
                strsd  =s.substring(n)+ s.substring(0,n);
                if (strsd.compareTo(minstrsd)<0)minstrsd=strsd;
            }
            return minstrsd;
        }else {
            sort(strs,strs.length);
            return new String(strs);
        }
    }


    public static void sort(char[] strs,int x){
        sortque(strs,0,x-1);
    }

    public static  void sortque(char[] strs,int begin,int last){
        if (begin==last)return;
        int midle = (begin+last)/2;
        sortque(strs,begin,midle);
        sortque(strs,midle+1,last);
        merge(strs,begin,midle,last);

    }
    public static  void merge(char[] str,int begin, int middle,int last){
        char[] strs = new char[last-begin+1];
        int i = begin; int j =middle+1;
        int k =0;
        while (i<=middle&&j<=last){
            if (str[i]<str[j]){
                strs[k]=str[i];
                i++;k++;
            }else {
                strs[k]=str[j];
                j++;k++;
            }
        }

        while (i<=middle){
            strs[k]=str[i];
            i++;k++;
        }

        while (j<=last){
            strs[k]=str[j];
            j++;k++;
        }

        int p = 0;

        for (int c = begin;c<=last;c++){
            str[c] =strs[p];
            p++;
        }
    }
}
